package com.share.algorithm.sort;

/**
 * @desc:希尔排序
 *   根据一个增量分段
 *   比如10个数，增量分别为n/2 = 5  2 1
 * @author:caifan
 * @date:2020/9/24
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arrays = {12, 4, 8, 7, 2, 10, 6, 9, 3, 5};
        shellSort(arrays);
    }


    /**
     * 希尔排序 [12, 4, 8, 7, 2, 10, 6, 9, 3, 5]
     * 第一次增量为10/2 = 5
     * 12 10
     * 4 6
     * 8 9
     * 7 3
     * 2 5
     * 第一次排序结果
     *  10  4  8  3  2    12 6 9  7  5
     *  插入排序
     *  2 3 4 8 10    5 6 7 9 12
     *
     *  第二次增量 5 / 2 = 2
     *  2 8 6 12
     *
     *  3 10 7
     *
     *  4 5 9
     *
     *  2 3 4 6 7 5 8 10 9 12 排序后结果
     *
     *  第三次增量 3 / 2 = 1
     *
     *  2 3 4 5 6 7 8 9 10 12
     *
     * @param arrays
     * @return
     */
    public static int[] shellSort(int[] arrays) {
        // 定义增量
        for (int gap = arrays.length / 2; gap > 0; gap = gap / 2) {
             //第一个数不用比较
            for (int i = gap; i < arrays.length; i++) {
                int data = arrays[i];
                int j = i - gap;
                for (; j >= 0; j -= gap) {//从尾到头，前面是排好序的，找到比它小的就不用找了
                    if (arrays[j] > data) {
                        arrays[j + gap] = arrays[j];//数据往后移动
                    } else {
                        break;//O(1)
                    }
                }
                arrays[j + gap] = data;

                System.out.println("第" + i + "次排序结果");
                for (j = 0; j < arrays.length; j++) {
                    System.out.print(arrays[j] + " ");
                }
                System.out.println();
            }
        }

        return arrays;

    }
}
